package com.yun.algorithmproblem.leetcode;

import java.util.PriorityQueue;

public class Leetcode1792 {
    public static void main(String[] args) {
        Leetcode1792 obj = new Leetcode1792();
        int[][] classes = {{1, 2}, {3, 5}, {2, 2}};
        int extraStudents = 2;
        System.out.println(obj.maxAverageRatio(classes, extraStudents));
    }

    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
                Long.compare((long) (b[1] - b[0]) * a[1] * (a[1] + 1), (long) (a[1] - a[0]) * b[1] * (b[1] + 1))
        );
        for (int[] c : classes) {
            pq.offer(new int[]{c[0], c[1]});
        }
        while (extraStudents-- > 0) {
            int[] c = pq.poll();
            c[0]++;
            c[1]++;
            pq.offer(c);
        }
        double res = 0;
        while (!pq.isEmpty()) {
            int[] c = pq.poll();
            res += (double) c[0] / c[1];
        }
        return res / classes.length;
    }
}
